class Solution {
    /*
        思路1：递归
        时间复杂度：O(N)，每个节点访问一次
        空间复杂度：O(N)，取决于递归的栈深度，栈深度在二叉树为一条链的时候会达到最大
    */
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        midShow(root);
        return list;
    }
    public void midShow(TreeNode root){
        if(root==null)
            return;
        midShow(root.left);
        list.add(root.val);
        midShow(root.right);
    }
}
class Solution {
    /*
        思路2：非递归遍历二叉树的办法（必须使用栈）
        原理：递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，
              其他都相同，具体实现可以看下面的代码。
    */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> st = new LinkedList<>();
        while( !st.isEmpty() || root!=null ){
            // 向左递归找到最左边的节点，并压入栈
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            if( !st.isEmpty() ){
                root = st.pop(); // 取出栈顶元素
                // ** 中序遍历的位置
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }
}